#include<iostream>
#include<string>
#include<vector>

using namespace std;

#include<iostream>
#include<string>
#include<vector>

using namespace std;

class Solution1 {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int>dp(n);//状态表示：dp[i]表示当前位置有多少种解码方式
        //初始化
        if (s[0] == '0')return 0;
        if (s.size() == 1 && s[0] != '0')return 1;//处理边界情况
        dp[0] = 1; dp[1] = 0;
        if ((s[0] - '0') * 10 + (s[1] - '0') >= 10 && (s[0] - '0') * 10 + (s[1] - '0') <= 26)dp[1]++;
            if (s[1] != '0')dp[1]++;

        for (int i = 2; i < n; i++)
        {
            if (dp[i] == 0 && dp[i - 1] == 0)return 0;//前两个位置都是零,说明没办法解码
            if (s[i] != '0')//当前位置不等于0，则加上前一个
            {
                dp[i] += dp[i - 1];
            }
            if ((s[i - 1] - '0') * 10 + (s[i] - '0') >= 10 && (s[i - 1] - '0') * 10 + (s[i] - '0') <= 26)
            {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n - 1];

    }
};




class Solution2 {
public:
    int numDecodings(string s) {
        int n=s.size();
        if(n==1)return s[0]-'0'!=0;
        vector<int>dp(n+1);
        dp[0]=1;//确保不影响后续结果
        dp[1]=s[0]-'0'!=0;
        for(int i=2;i<=n;i++)
        {
            if(dp[i-2]==0&&dp[i-1]==0)//说明无法解码
            {
                return 0;
            }
            if(s[i-1]!='0')dp[i]+=dp[i-1];
            if((s[i-2]-'0')*10+(s[i-1]-'0')>=10&&(s[i-2]-'0')*10+(s[i-1]-'0')<=26)
            {
                dp[i]+=dp[i-2];
            }
        }
        return dp[n];
        
    }
};